import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DickYang
 * Date: 2023-07-18
 * Time: 20:46
 */
public class MyHeap {
    public int[] elme;
    public int usedSize;

    public MyHeap() {
        this.elme = new int[10];
    }

    //初始化数组
    public void initHeap(int[] arrya) {
        for (int i = 0; i < arrya.length; i++) {
            this.elme[i] = arrya[i];
            usedSize++;
        }
    }

    //创建大根堆
    public void createBigHeap(int[] arrya){
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftDownBig(parent,usedSize);
        }
    }
    private void shiftDownBig(int parent,int len) {
        int child = 2*parent+1;//左孩子
        while(child < len) { // 最起码一定有左孩子
            if(child+1 <len && this.elme[child] < this.elme[child+1]) {
                child++; // 一定有右孩子,并且右孩子比左孩子大
            }
            //判断最大的孩子与parent交换
            if (this.elme[child] > this.elme[parent]) {
                //孩子大于parent 交换
                int tmp = this.elme[child];
                this.elme[child] = this.elme[parent];
                this.elme[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }
    //创建小根堆
    public void createSmallHeap(int[] arrya){
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {
            shiftDownSmall(parent,usedSize);
        }
    }
    private void shiftDownSmall(int parent,int len) {
        int child = 2*parent+1;//左孩子
        while(child < len) { // 最起码一定有左孩子
            if(child+1 < len && this.elme[child] > this.elme[child+1]) {
                child++; // 一定有右孩子,并且右孩子比左孩子小
            }
            //判断最小的孩子与parent交换
            if (this.elme[child] < this.elme[parent]) {
                //孩子小于parent 交换
                int tmp = this.elme[child];
                this.elme[child] = this.elme[parent];
                this.elme[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            } else {
                break;
            }
        }
    }

    //插入元素  时间复杂度为: O(N*logN)
    public void offer(int val) {
        //判断数组是否为满
        if (isFull()) {
            this.elme = Arrays.copyOf(this.elme,2*this.elme.length);
        }
        this.elme[usedSize++] = val;
        shiftUp(usedSize-1);
    }
    private void shiftUp(int child) {
        int parent = (child-1)/2;
        while(parent >= 0) {
            if (this.elme[child] > this.elme[parent]) {
                int tmp = this.elme[child];
                this.elme[child] = this.elme[parent];
                this.elme[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull() {
        return usedSize == this.elme.length;
    }

    //删除元素
    public void pop() {
        if (isEmpty()) {//数组为空
            return;
        }

        int tmp = this.elme[0];
        this.elme[0] = this.elme[usedSize-1];
        this.elme[usedSize-1] = tmp;

        usedSize--;
        shiftDownBig(0,usedSize);

    }
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //获取堆顶元素
    public int peek() {
        return this.elme[0];
    }


    //前K个最大的元素 N*logK
    public int[] maxK(int[] arr,int k) {
        int[] ret = new int[k];
        if (arr == null || k == 0) {
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k); // 优先级队列默认为小根堆存放

        //遍历数组的前K个元素,放到小根堆中 K * logK
        for (int i = 0; i < k; i++) {
            minHeap.offer(arr[i]);
        }
        //遍历剩下的K-1个元素.与堆顶元素比较,如果比堆顶小,则放入堆中 (N-K) * logK
        for (int i = k ;i < arr.length; i++) {
            if (arr[i] > minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        //把前K个最大的元素放入到数组中
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    public void HeapSort(int[] array) {
        int end = usedSize-1;
        while(end > 0) {

            int tmp = this.elme[end];
            this.elme[end] = this.elme[0];
            this.elme[0] = tmp;
            //调整为大根堆
            shiftDownBig(0,end);
            end--;
        }
    }
}
